// Given a string, find the length of the longest substring without repeating characters.

#include <stdio.h>
#include <string>
#include <map>
using std::string;
using std::map;

int lengthOfLongestSubstring(string s) {
    if (s == "") return 0;
    int l = s.size();
    int maxl = 0;
    // use a hash to record each element's last slot
    map<char, int> m;
    int start = 0;
    for (int i = 0; i < l; ++i) {
        if (m.count(s[i]) != 0 && m[s[i]] >= start) {
            maxl = maxl < i - start ? i - start : maxl;
            start = m[s[i]] + 1;
        }
        m[s[i]] = i;
    }
    maxl = maxl < l - start ? l - start : maxl;
    return maxl;
}

int main() {
    string s = "abcabcbb";
    printf("%s(3) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "pwwkew";
    printf("%s(3) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "bbbbb";
    printf("%s(1) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "";
    printf("%s(0) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "abcdefg";
    printf("%s(4) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "a";
    printf("%s(1) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "aab";
    printf("%s(2) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "abb";
    printf("%s(2) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
    s = "abba";
    printf("%s(2) : %d\n", s.c_str(), lengthOfLongestSubstring(s));
}

